#pragma once
#include <iostream>
#include <vector>
#include "assert.h"
using namespace std;

enum color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _parent;
	color _col;
	RBTreeNode(const T& data)
		:_data(data)
		, _right(nullptr)
		, _left(nullptr)
		, _parent(nullptr)
	{}
};

template<class T>
struct RBTreeIterator
{
	typedef RBTreeNode Node;
	typedef RBTreeIterator<T> Self;
	Node* _node;
	RBTreeIterator(Node* node)
		:_node(node)
	{}
	Self& operator++()
	{
		if (_node->_right)
		{
			Node* leftmost = _node->_right;
			while (leftmost->_left)
			{
				leftmost = leftmost->_left;
			}
			_node = leftmost;
		}
		else
		{
			cur = _node;
			parent = cur->_parnet;
			while (parnet && cur == parnet->_right)
			{
				cur = parent;
				parent = cur->_parnet;
			}
			_node = parent;
		}
		return *this;
	}
};

template<class K,class T,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	Iterator begin()
	{
		Node* leftmost = _root;
		while (leftmost && leftmost->_left)
		{
			leftmost = leftmost->_left;
		}
		return Iterator(leftmost);
	}
	bool insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new(data);
			_root->_col = BLACK;
			return true;
		}
		KeyOfRT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		cur->_col =RED;
		if (kof(parent->_data) < kof(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parnet);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					braeak;
				}

			}
		}
		_root->_col = BLACK;
		return true;

	}
private:
	Node* _root = nullptr;
};
